package Amazon;

import java.util.Arrays;

/**
 * Write a function that given an input array of integers with 4 entries and a desired target_sum, 
 * returns the number of combinations , of any length, that add up to that target_sum.
 *
 * Bonus question
 * How would you extend it to deal with a varying length input array?
 * @author Yue Chi
 *
 */
public class AmazonSE {

	public static int ret = 0;	//static value to count the number of combination.
	/**
	 * Return the number of combinations that add up to target_sum.
	 * If the array is {-1,0,1,0}, we assume that this two 0 is the same. That means {0} and {0} is the same
	 * but {-1,1,0} and {-1,1,0,0} is different.
	 * 
	 * @param A					the input array A contains vary number of elements, also include 4.
	 * @param target_sum		target_sum
	 * @return					the number of combinations.
	 * 	
	 */
	public int solution(int[] A, int target_sum){
		if(A==null || A.length==0)	//if A is empty, return 0
			return 0;			
		boolean isAct = false;		//if there has a element be chosen.
		ret = 0;
		Arrays.sort(A);				//sort the array first.
		helper(A, target_sum, 0, isAct);
		return ret;
	}

	/**
	 * Recursively count the number of combinations.
	 * @param input		the array
	 * @param sum		current sum----should be long to avoid overflows
	 * @param start		current start point
	 * @param isAct		is there any of the element be chosen
	 */
	private void helper(int[] input, long sum, int start, boolean isAct){
		if(sum==0 && isAct){
			ret++;
		}
		for(int i=start;i<input.length;++i){
			if(input[i]>sum)
				break;
			sum = sum - input[i];
			helper(input, sum, i+1, true);
			sum = sum + input[i];
			while(i<input.length-1 && input[i]==input[i+1]){//avoid duplicate chosen
				++i;
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		AmazonSE test = new AmazonSE();
		int[] A = {Integer.MAX_VALUE,1,-1,Integer.MIN_VALUE};
		int res1 = test.solution(A, -1);
		System.out.println(res1);
		
		int[] B = {-1,0,1,0};
		int res2 = test.solution(B, 0);
		System.out.println(res2);
	}

}
